package j2024.j202409;

public class j0910 {
    /**
     * 55. 跳跃游戏
     * @param nums
     * @return
     */
    public boolean canJump(int[] nums) {
        int left = 0,right = 0,maxPos = 0,n = nums.length;
        while(left<=right){
            if(maxPos>=n-1){
                return true;
            }
            for (int i = left; i <= right; i++) {
                maxPos = Math.max(maxPos,nums[i]+i);
            }
            left = right+1;
            right = maxPos;
        }
        return false;
    }

    /**
     * 134. 加油站
     * @param gas
     * @param cost
     * @return
     */
    public static int canCompleteCircuit1(int[] gas, int[] cost) {
        int n = gas.length;
        int[] diff = new int[n];
        for (int i = 0; i < n; i++) {
            diff[i] = gas[i]-cost[i];
        }
        for (int i = 0; i < n; i++) {
            if(diff[i]>=0){
                if(com(diff,i)){
                    return i;
                }
            }
        }
        return -1;
    }
    public static boolean com(int[] diff,int begin){
        int count = diff[begin];
        int i = begin+1;
        while(i!=begin){
            if(i>=diff.length){
                i = 0;
                continue;
            }
            count+=diff[i++];
            if(count<0){
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int[] gas = {3,1,1};
        int[] cost = {1,2,2};
        canCompleteCircuit1(gas,cost);
    }
    public int canCompleteCircuit2(int[] gas, int[] cost) {
        int n = gas.length;
        for (int i = 0; i < n; i++) {
            int rest = 0;
            int step = 0;
            for (; step < n; step++) {
                int index = (step+i)%n;
                rest = rest+gas[index]-cost[index];
                if(rest<0){
                    break;
                }
            }
            if(rest>=0){
                return i;
            }
            i = i+step;
        }
        return -1;
    }

    /**
     * 738. 单调递增的数字
     * @param n
     * @return
     */
    public int monotoneIncreasingDigits(int n) {
        char[] s = Integer.toString(n).toCharArray();
        int i = 0,m = s.length;
        while(i+1<m && s[i]<=s[i+1]){
            i++;
        }
        if(i==m-1){
            return n;
        }
        while(i-1>=0 && s[i] == s[i-1]){
            i--;
        }
        s[i]--;
        for (int j = i+1; j < m; j++) {
            s[j]='9';
        }
        return Integer.parseInt(new String(s));
    }
}
